//给你一个二叉树的根节点 root。设根节点位于二叉树的第 1 层，而根节点的子节点位于第 2 层，依此类推。 
//
// 请返回层内元素之和 最大 的那几层（可能只有一层）的层号，并返回其中 最小 的那个。 
//
// 
//
// 示例 1： 
//
// 
//
// 
//输入：root = [1,7,0,7,-8,null,null]
//输出：2
//解释：
//第 1 层各元素之和为 1，
//第 2 层各元素之和为 7 + 0 = 7，
//第 3 层各元素之和为 7 + -8 = -1，
//所以我们返回第 2 层的层号，它的层内元素之和最大。
// 
//
// 示例 2： 
//
// 
//输入：root = [989,null,10250,98693,-89388,null,null,null,-32127]
//输出：2
// 
//
// 
//
// 提示： 
//
// 
// 树中的节点数在
// [1, 10⁴]范围内
// 
// -10⁵ <= Node.val <= 10⁵ 
// 
//
// Related Topics 树 深度优先搜索 广度优先搜索 二叉树 👍 124 👎 0


package LeetCode.editor.cn;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

/**
 * @author ldltd
 * @date 2023-10-02 18:20:44
 * @description 1161.最大层内元素和
 */
public class MaximumLevelSumOfABinaryTree{
	 public static void main(String[] args) {
	 	 //测试代码
	 	 Solution solution = new MaximumLevelSumOfABinaryTree().new Solution();

	 }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)

  //Definition for a binary tree node.
  public class TreeNode {
     int val;
     TreeNode left;
      TreeNode right;
     TreeNode() {}
     TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
         this.val = val;
          this.left = left;
          this.right = right;
      }
  }

class Solution {
		 /*层次遍历*/
    public int maxLevelSum1(TreeNode root) {
		Deque<TreeNode> q=new LinkedList<>();
		int max=root.val,res=1,t=0,lel=1,tem=0;
		q.offer(root);
		while (!q.isEmpty()){
			t=q.size();
			tem=0;
			while (t>0){
				TreeNode poll = q.poll();
				if(poll.left!=null){
					q.offer(poll.left);
				}
				if(poll.right!=null){
					q.offer(poll.right);
				}
				t--;
				tem+=poll.val;
			}
			if(tem>max) {
				max=tem;
				res=lel;
			}
			lel++;

		}
		return res;
    }

	private List<Integer> sum = new ArrayList<Integer>();
	//dfs，这里用了动态数组，每一层有一个值，如果当前的层次和数组长度相等，说明他第一次访问到当前层次，则加入list，否则就修改当前层次的值
	public int maxLevelSum(TreeNode root) {
		dfs(root, 0);
		int ans = 0;
		for (int i = 0; i < sum.size(); ++i) {
			if (sum.get(i) > sum.get(ans)) {
				ans = i;
			}
		}
		return ans + 1; // 层号从 1 开始
	}

	private void dfs(TreeNode node, int level) {
		if (level == sum.size()) {
			sum.add(node.val);
		} else {
			sum.set(level, sum.get(level) + node.val);
		}
		if (node.left != null) {
			dfs(node.left, level + 1);
		}
		if (node.right != null) {
			dfs(node.right, level + 1);
		}
	}

}
//leetcode submit region end(Prohibit modification and deletion)

}
